<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>【KM算法】B - Going Home POJ - 2195.md | 蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。 https:&#x2F;&#x2F;vjudge.net&#x2F;contest&#x2F;389071#problem&#x2F;B  题目描述">
<meta property="og:type" content="article">
<meta property="og:title" content="【KM算法】B - Going Home POJ - 2195.md">
<meta property="og:url" content="http://example.com/1111/11/11/%E3%80%90KM%E7%AE%97%E6%B3%95%E3%80%91B%20-%20Going%20Home%20POJ%20-%202195/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:description" content="说明 - 2022-05-05 本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。 https:&#x2F;&#x2F;vjudge.net&#x2F;contest&#x2F;389071#problem&#x2F;B  题目描述">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="1111-11-11T03:06:11.000Z">
<meta property="article:modified_time" content="2022-05-06T07:16:52.572Z">
<meta property="article:author" content="StarsWhisper">
<meta property="article:tag" content="OldBlog(Before20220505)">
<meta property="article:tag" content="二分图">
<meta property="article:tag" content="KM算法">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main"><article id="post-【KM算法】B - Going Home POJ - 2195" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/1111/11/11/%E3%80%90KM%E7%AE%97%E6%B3%95%E3%80%91B%20-%20Going%20Home%20POJ%20-%202195/" class="article-date">
  <time class="post-time" datetime="1111-11-11T03:06:11.000Z" itemprop="datePublished">
    <span class="post-month">11月</span><br/>
    <span class="post-day">11</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      【KM算法】B - Going Home POJ - 2195.md
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>,<a class="article-category-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%9B%BE%E8%AE%BA/">图论</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="说明-2022-05-05"><a class="markdownIt-Anchor" href="#说明-2022-05-05"></a> 说明 - 2022-05-05</h2>
<p>本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。</p>
<p><a target="_blank" rel="noopener" href="https://vjudge.net/contest/389071#problem/B">https://vjudge.net/contest/389071#problem/B</a></p>
<h2 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h2>
<p>On a grid map there are n little men and n houses. In each unit time, every<br />
little man can move one unit step, either horizontally, or vertically, to an<br />
adjacent point. For each little man, you need to pay a $1 travel fee for every<br />
step he moves, until he enters a house. The task is complicated with the<br />
restriction that each house can accommodate only one little man.</p>
<p>Your task is to compute the minimum amount of money you need to pay in order<br />
to send these n little men into those n different houses. The input is a map<br />
of the scenario, a ‘.’ means an empty space, an ‘H’ represents a house on that<br />
point, and am ‘m’ indicates there is a little man on that point.</p>
<p>![在这里插入图片描述](<a target="_blank" rel="noopener" href="https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai56MTgwLmNuLzI5ZGE0YzIyY2Q5YTM1ZWI5NmIyYTA4Yjc1Y2U4NDIw?x-oss-">https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai56MTgwLmNuLzI5ZGE0YzIyY2Q5YTM1ZWI5NmIyYTA4Yjc1Y2U4NDIw?x-oss-</a><br />
process=image/format,png#pic_center)</p>
<p>You can think of each point on the grid map as a quite large square, so it can<br />
hold n little men at the same time; also, it is okay if a little man steps on<br />
a grid with a house without entering that house.</p>
<h2 id="输入"><a class="markdownIt-Anchor" href="#输入"></a> 输入</h2>
<p>There are one or more test cases in the input. Each case starts with a line<br />
giving two integers N and M, where N is the number of rows of the map, and M<br />
is the number of columns. The rest of the input will be N lines describing the<br />
map. You may assume both N and M are between 2 and 100, inclusive. There will<br />
be the same number of 'H’s and 'm’s on the map; and there will be at most 100<br />
houses. Input will terminate with 0 0 for N and M.</p>
<h2 id="输出"><a class="markdownIt-Anchor" href="#输出"></a> 输出</h2>
<p>For each test case, output one line with the single integer, which is the<br />
minimum amount, in dollars, you need to pay.</p>
<h2 id="样例输入"><a class="markdownIt-Anchor" href="#样例输入"></a> 样例输入</h2>
<p>2 2<br />
.m<br />
H.<br />
5 5<br />
HH…m<br />
…<br />
…<br />
…<br />
mm…H<br />
7 8<br />
…H…<br />
…H…<br />
…H…<br />
mmmHmmmm<br />
…H…<br />
…H…<br />
…H…<br />
0 0</p>
<h2 id="样例输出"><a class="markdownIt-Anchor" href="#样例输出"></a> 样例输出</h2>
<p>2<br />
10<br />
28</p>
<h2 id="瞎翻译"><a class="markdownIt-Anchor" href="#瞎翻译"></a> 瞎翻译</h2>
<p>给你一张地图，地图被分割成了N行M列的网格。</p>
<p>第一行：输入N，M表示地图大小。</p>
<p>第2 到 第N+1行： 输入地图内容， .代表空地，m代表人，H代表房子。</p>
<p>N和M不大于100，房子数目不大于100</p>
<p>人和房子的数量是相等的，而人要移动进入房子，且每个房子只能进一个人。<br />
不过人每移动一格（横移或者竖移）要花一块钱。</p>
<p><strong>问：</strong><br />
要使人都进入房子最少花多少钱？<br />
（地图的每一格都足够大，可以容纳无限多的人。）</p>
<h2 id="题解"><a class="markdownIt-Anchor" href="#题解"></a> 题解</h2>
<p>思路：<br />
<strong>1.</strong><br />
地图最大为100x100 ，所以人最多花不到200元钱，我们定一个常数ML=210.<br />
<strong>2.</strong><br />
先计算每个人到每个房子需要花的钱，用ML减去需要花的钱，得到的数值，存进数组map[][]（不是地图，我取的映射的意思）</p>
<p>这么存的原因是：KM算法可以算出最多要花多少钱，然而我们需要求最少要花多少钱，这样就只需要把“最小的”先暂时变成“最大的”，完成KM算法之后再额外通过一步计算得到正确答案。</p>
<p>推导可知：正确答案=（ML*房子数量）-KM算法得到的最大值</p>
<p>​<br />
​    #include <cstdio><br />
​    #include <iostream><br />
​    #include <algorithm><br />
​    #include <cstring><br />
​<br />
const int maxn=110;<br />
const int ML=220;//花费不可能超过200<br />
char cell[maxn][maxn];<br />
int map[maxn][maxn],lx[maxn],ly[maxn],link[maxn];<br />
//map取的意思是映射，map[i][j]表示第i个人到第j个房子的距离<br />
//lx表示人顶标的值，ly表示房子顶标的值<br />
bool visx[maxn],visy[maxn];<br />
int pnum,ans;<br />
struct Node<br />
{<br />
int x,y;<br />
}person[maxn],house[maxn];</p>
<pre><code>bool dfs(int x)
&#123;

    visx[x]=true;
    for(int i=0; i&lt;pnum ;i++)
    &#123;
//这里的lx[x]一开始写成了lx[i]，找bug找了半天，巨麻烦，打标记警醒一下
        if(!visy[i] &amp;&amp; lx[x]+ly[i]==map[x][i])
        &#123;
            visy[i]=true;
            if(link[i]==-1 || dfs(link[i]))
            &#123;
                link[i]=x;
                return true;
            &#125;
        &#125;
    &#125;
    return false;
&#125;

int km()
&#123;
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    memset(link,-1,sizeof(link));
    for(int i=0; i&lt;pnum ; i++)
        for(int j=0; j&lt;pnum; j++)
        &#123;
            lx[i]=std::max(lx[i],map[i][j]);
        &#125;
    for(int i=0; i&lt;pnum; i++)
    &#123;
        memset(visx,false,sizeof(visx));
        memset(visy,false,sizeof(visy));
        while(!dfs(i))
        &#123;
            int tmp=ML;

//---------------------------&gt;&gt;特此标记&lt;&lt;-----------------------------
// KM没学好，这里一开始想错了，误认为下面tmp=min（）式子中lx的下标一定是i，
//导致下方两行没要，一直错被卡了很长时间

            for(int j=0; j&lt;pnum; j++)
                if(visx[j])
//*******************************************************************************
                    for(int k=0; k&lt;pnum; k++)
                        if(visy[k]==false)
                            tmp=std::min(tmp,lx[j]+ly[k]-map[j][k]);
            for(int j=0; j&lt;pnum; j++)
            &#123;
                if(visx[j])
                    lx[j]-=tmp;
                if(visy[j])
                    ly[j]+=tmp;
            &#125;
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
        &#125;
    &#125;
    ans=0;
    for(int i=0;i&lt;pnum; i++)
    &#123;
        ans+=lx[i]+ly[i];
    &#125;
    return ML*pnum-ans;
&#125;

int main()
&#123;
    int n,m;
    int p,h;
    while(std::cin &gt;&gt; n &gt;&gt; m &amp;&amp; !(n==0 &amp;&amp; m==0))
    &#123;
        p=h=0;
        for(int i=0;i &lt;n; i++)
            for(int j=0; j&lt;m ; j++)
            &#123;
                std::cin &gt;&gt; cell[i][j];
                if(cell[i][j]=='m')
                &#123;
                    person[p].x=i;
                    person[p++].y=j;
                &#125;
                else if(cell[i][j]=='H')
                &#123;
                    house[h].x=i;
                    house[h++].y=j;
                &#125;
            &#125;
        pnum=p;
        for(int i=0; i&lt;p; i++)
            for(int j=0; j&lt;h; j++)
            &#123;
                map[i][j]=abs(person[i].x-house[j].x)+abs(person[i].y-house[j].y);
                map[i][j]=ML-map[i][j];
            &#125;
        std::cout &lt;&lt; km() &lt;&lt; std::endl;
    &#125;

    return 0;
&#125;
</code></pre>
<p>​</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/1111/11/11/%E3%80%90KM%E7%AE%97%E6%B3%95%E3%80%91B%20-%20Going%20Home%20POJ%20-%202195/" data-id="cl2uhoebx0015e4j3021z83ha" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/KM%E7%AE%97%E6%B3%95/" rel="tag">KM算法</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/OldBlog-Before20220505/" rel="tag">OldBlog(Before20220505)</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E4%BA%8C%E5%88%86%E5%9B%BE/" rel="tag">二分图</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/1111/11/11/%E3%80%90DP%E3%80%91%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          【DP】石子合并.md
        
      </div>
    </a>
  
  
    <a href="/1111/11/11/%E3%80%90LCA%E7%BB%83%E4%B9%A0%20%E5%80%8D%E5%A2%9E%20tarjin%E3%80%91%20%E6%B4%9B%E8%B0%B7P3379%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%20P1967%E8%B4%A7%E8%BD%A6%E8%BF%90%E8%BE%93/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">【LCA练习 倍增 tarjin】 洛谷P3379【模板】最近公共祖先 P1967货车运输.md</div>
    </a>
  
</nav>

  
</article>



</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>